Tree data storage structures such as B-trees and variations of B-trees (e.g., B*trees, B+trees, B−link trees) and others are used for storing large files of information on secondary storage and for supporting insertion, lookup, deletion, and enumeration operations. Such tree data storage structures are typically implemented on individual computers, with each computer satisfying operations involving its structure without regard to information indexed by tree data storage structures on other computers. That is, each computer includes its own tree data storage structure and does not, for example, retrieve information contained in nodes of a tree data storage structure located on a second computer even if the computers are communicatively coupled.
For purposes of fault tolerance, performance, scalability, and information sharing, it is desirable to utilize tree data storage structures in a distributed environment such as a cluster of machines on a network. Implementation of tree data storage structures in a distributed environment should promote efficient information sharing through efficient and highly concurrent B-Tree operations.